package com.honeywen.mymvc.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 141. 环形链表
 * https://leetcode-cn.com/problems/linked-list-cycle/
 * @author wangwei
 * @date 2018/12/21 下午4:43
 */
public class CycleListNode {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        node1.next = node2;
        node2.next = node1;

        System.out.println(123);

        System.out.println(hasCycle(node1));
        System.out.println(hasCycle2(node1));
        System.out.println(hasCycle3(node1));

    }

    public static boolean hasCycle3(ListNode head) {

        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        do {
            fast = fast.next.next;
            slow = slow.next;

        } while (fast != null && fast.next != null && fast != slow);

        return fast == slow ? true : false;

    }
    public static boolean hasCycle2(ListNode head) {

        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            boolean flag = set.add(head);
            if (!flag) {
                return true;
            }
            head = head.next;
        }


        return false;

    }
    public static boolean hasCycle(ListNode head) {

        if (head == null || head.next == null) {
            return false;
        }

        List<ListNode> list = new ArrayList<>();

        while (head != null) {
            if (list.contains(head)) {
                return true;
            }
            list.add(head);
            head = head.next;
        }


        return false;
    }
}
